package Tree;

import java.util.*;

public class _652_FindDuplicateSubtrees {

    //time limit exceeded
    List<TreeNode> res = new ArrayList<>();
    //consider the situation that the two number has different subtree:4-1-3,4-5-2
    Set<TreeNode> duplicate = new HashSet<>();
    public List<TreeNode> findDuplicateSubtrees_1(TreeNode root) {
        traversal(root,root);
        return res;
    }

    public void traversal(TreeNode nodes1, TreeNode nodes2) {
        if (nodes1 != null && nodes2 != null) {
            if (nodes1 != nodes2) {
                if (compare(nodes1, nodes2)) {
                    if (!duplicate.contains(nodes1) && !duplicate.contains(nodes2)) {
                        res.add(nodes1);
                    }
                    duplicate.add(nodes1);
                    duplicate.add(nodes2);
                }
            }
            traversal(nodes1,nodes2.left);
            traversal(nodes1, nodes2.right);
            traversal(nodes2, nodes1.left);
            traversal(nodes2, nodes1.right);
        }
    }
    public boolean compare(TreeNode nodes1, TreeNode nodes2) {
        if (nodes1 == null && nodes2 == null) {
            return true;
        } else if (nodes1 != null && nodes2 != null) {
            if (nodes1.val == nodes2.val) {
                return compare(nodes1.left, nodes2.left) && compare(nodes1.right, nodes2.right);
            } else {
                return false;
            }
        } else {
            return false;
        }
    }

    //reference solution:change nodes to string
    Map<String,Integer> count;
    List<TreeNode> ans;
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        count = new HashMap<>();
        ans = new ArrayList<>();
        collect(root);
        return ans;
    }

    public String collect(TreeNode root) {
        if(root==null) return "#";
        String value = root.val + collect(root.left) + collect(root.right);
        count.put(value, count.getOrDefault(value, 0) + 1);
        if (count.get(value) == 2) {
            ans.add(root);
        }
        return value;
    }
}
